package gold.digger;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC1994 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {

        Map<Integer, Set<Integer>> primeMap = new HashMap<>();
        int factor = 1000000007;

        Solution() {
            primeMap.put(2, new HashSet<>(Arrays.asList(2)));
            primeMap.put(3, new HashSet<>(Arrays.asList(3)));
            primeMap.put(5, new HashSet<>(Arrays.asList(5)));
            primeMap.put(6, new HashSet<>(Arrays.asList(2, 3)));
            primeMap.put(7, new HashSet<>(Arrays.asList(7)));
            primeMap.put(10, new HashSet<>(Arrays.asList(2, 5)));
            primeMap.put(11, new HashSet<>(Arrays.asList(11)));
            primeMap.put(13, new HashSet<>(Arrays.asList(13)));
            primeMap.put(14, new HashSet<>(Arrays.asList(2, 7)));
            primeMap.put(15, new HashSet<>(Arrays.asList(3, 5)));
            primeMap.put(17, new HashSet<>(Arrays.asList(17)));
            primeMap.put(19, new HashSet<>(Arrays.asList(19)));
            primeMap.put(21, new HashSet<>(Arrays.asList(3, 7)));
            primeMap.put(22, new HashSet<>(Arrays.asList(2, 11)));
            primeMap.put(23, new HashSet<>(Arrays.asList(23)));
            primeMap.put(26, new HashSet<>(Arrays.asList(2, 13)));
            primeMap.put(29, new HashSet<>(Arrays.asList(29)));
            primeMap.put(30, new HashSet<>(Arrays.asList(2, 3, 5)));
        }

        public int numberOfGoodSubsets(int[] nums) {
            TreeMap<Integer, Integer> cntMap = new TreeMap<>();
            int oneCnt = 0;
            for (int num : nums) {
                if (1 == num) oneCnt++;
                if (primeMap.containsKey(num)) {
                    cntMap.put(num, cntMap.getOrDefault(num, 0) + 1);
                }
            }

            List<Integer> candidateList = new ArrayList<>(cntMap.keySet());
            Set<Integer> curAddedPrimeSet = new HashSet<>();
            long ans = dfs(candidateList, 0, curAddedPrimeSet, cntMap);
            long oneMulti = 1L;
            for (int i = 0; i < oneCnt; i++) oneMulti = (oneMulti * 2) % factor;
            return (int) (oneMulti * ans % factor); // 每一个不含1的有效方案，都可以配合上零或多个1。因此最终结果还要乘上 1 < <numOfOnes
        }

        public long dfs(List<Integer> candidateList, int curPos, Set<Integer> curAddedPrimeSet, TreeMap<Integer, Integer> cntMap) {
            if (curPos >= candidateList.size()) return curAddedPrimeSet.size() > 0 ? 1 : 0;
            // 当前 curPos 有两种策略 ： 1 不选入 curAddedPrimeSet， 2 进入curAddedPrimeSet但需要判断当前是否可以加入
            long notChooseCur = dfs(candidateList, curPos + 1, curAddedPrimeSet, cntMap);
            long chooseCur = 0;

            Set<Integer> retainSet = new HashSet<>();
            retainSet.addAll(curAddedPrimeSet);
            retainSet.retainAll(primeMap.get(candidateList.get(curPos)));
            if (retainSet.size() <= 0) {
                // 当前可以加入，curAddedPrimeSet 加入当前元素的素数集合
                curAddedPrimeSet.addAll(primeMap.get(candidateList.get(curPos)));
                chooseCur = cntMap.get(candidateList.get(curPos)) * dfs(candidateList, curPos + 1, curAddedPrimeSet, cntMap);
                curAddedPrimeSet.removeAll(primeMap.get(candidateList.get(curPos))); // 返回时去除
            }

            return (notChooseCur + chooseCur) % factor;
        }
    }

    class Solution_Other {
        long res = 0;
        final int INF = 1000000007;
        Map<Integer, Set<Integer>> factor;

        public int numberOfGoodSubsets(int[] nums) {
            int[] map = new int[31];    // 只与元素个数有关 因此用map存起来
            for (int n : nums)
                map[n]++;
            factor = new HashMap<>();   // 存储30以内每个元素的不能共存的因子
            init(factor);
            // 2~30的所有情况
            dfs(map, 2, 1L, new HashSet<>());
            res--;  // 去掉空元素的情况
            // 数字1的情况 可以用多次数字1
            long cnt1 = 1L;
            for (int i = 0; i < map[1]; i++)
                cnt1 = (cnt1 << 1) % INF;   // 防止溢出2^map[1]
            return (int) ((cnt1 * res) % INF);
        }

        // idx:2~30当前元素 curS:当前的元素集合 curN:形成当前集合的情况数
        public void dfs(int[] map, int idx, long curN, Set<Integer> curS) {
            if (idx == 31) {
                res = (res + curN) % INF;
                return;
            }
            boolean canBeChosen = true;
            if (map[idx] == 0 || !factor.containsKey(idx)) { // 原数组中不存在该元素或本身不满足条件的元素 直接跳过
                dfs(map, idx + 1, curN, curS);
                return;
            }
            for (int fac : curS) {   // 当前集合是否存在idx元素的因子
                if (factor.get(idx).contains(fac)) {
                    canBeChosen = false;
                    break;
                }
            }
            // 回溯
            if (canBeChosen) {
                long tmp = (curN * map[idx]) % INF;
                for (int f : factor.get(idx))    // 添加当前元素的因子
                    curS.add(f);
                curS.add(idx);  // 添加自身
                dfs(map, idx + 1, tmp, curS);
                for (int f : factor.get(idx))
                    curS.remove(f);
                curS.remove(idx);
            }
            // 当前元素未被选中的情况
            dfs(map, idx + 1, curN, curS);
        }

        // 注意到有些元素自身分解就已不满足条件
        public void init(Map<Integer, Set<Integer>> factor) {
            factor.put(2, new HashSet<>());
            factor.put(3, new HashSet<>());
            factor.put(5, new HashSet<>());
            factor.put(6, new HashSet<>(Arrays.asList(2, 3)));
            factor.put(7, new HashSet<>());
            factor.put(10, new HashSet<>(Arrays.asList(2, 5)));
            factor.put(11, new HashSet<>());
            factor.put(13, new HashSet<>());
            factor.put(14, new HashSet<>(Arrays.asList(2, 7)));
            factor.put(15, new HashSet<>(Arrays.asList(3, 5)));
            factor.put(17, new HashSet<>());
            factor.put(19, new HashSet<>());
            factor.put(21, new HashSet<>(Arrays.asList(7, 3)));
            factor.put(22, new HashSet<>(Arrays.asList(2, 11)));
            factor.put(23, new HashSet<>());
            factor.put(26, new HashSet<>(Arrays.asList(2, 13)));
            factor.put(29, new HashSet<>());
            factor.put(30, new HashSet<>(Arrays.asList(2, 3, 5, 6, 10, 15)));
        }
    }

    public void run() {
        Solution solution = new Solution();
        Solution_Other solution_other = new Solution_Other();
        System.out.println(solution.numberOfGoodSubsets(InputUtil.toIntegerArray("[1,2,3,4]")));
        System.out.println(solution.numberOfGoodSubsets(InputUtil.toIntegerArray("[4,2,3,15]")));
        System.out.println(solution.numberOfGoodSubsets(InputUtil.toIntegerArray("[5,10,1,26,24,21,24,23,11,12,27,4,17,16,2,6,1,1,6,8,13,30,24,20,2,19]")));
        System.out.println(solution_other.numberOfGoodSubsets(InputUtil.toIntegerArray("[5,10,1,26,24,21,24,23,11,12,27,4,17,16,2,6,1,1,6,8,13,30,24,20,2,19]")));
        System.out.println(solution.numberOfGoodSubsets(InputUtil.toIntegerArray("[1,26,1,1,21,1,3,13,1,1,1,26,29,29,6,10,29,1,1,11,15,6,14,1,17,1,1,30,21,1,17,1,1,1,23,1,7,17,15,1,1,1,14,22,11,22,17,1,19,1,2,21,29,1,22,1,1,14,22,1,14,1,1,1,1,17,1,1,1,3,1,14,19,1,1,1,1,21,26,1,1,1,13,1,1,30,21,1,1,1,1,7,1,1,7,13,6,1,29,29,1,1,23,1,19,10,10,1,1,2,1,1,23,15,5,15,1,1,19,15,1,1,14,1,7,26,1,1,2,13,19,1,3,22,1,1,29,1,7,1,1,1,1,3,1,1,1,3,1,1,1,2,17,1,1,1,1,1,19,5,1,1,1,19,30,23,1,1,2,1,1,7,17,1,1,1,30,21,1,3,1,5,15,1,26,1,1,21,22,19,1,13,6,15,19,2,1,1,1,1,11,17,21,29,23,26,10,1,30,1,14,1,1,21,1,30,1,1,1,11,22,19,21,30,11,14,1,1,3,7,17,10,10,3,1,1,1,10,1,15,1,15,15,1,1,1,1,1,21,14,6,1,17,1,1,1,17,10,3,1,22,21,1,1,23,19,1,5,5,5,10,1,29,1,1,1,1,7,1,15,1,6,6,1,1,1,13,1,1,29,17,1,1,1,6,1,1,2,13,10,29,1,13,21,7,10,1,1,1,7,29,15,29,17,5,30,1,11,1,23,1,1,1,5,1,30,6,1,5,6,1,11,17,26,1,1,13,1,26,1,11,13,1,11,1,1,1,30,1,1,1,14,19,1,1,15,21,1,1,2,1,1,19,1,26,1,5,22,13,1,1,11,7,29,3,26,30,19,10,1,7,1,22,1,6,2,1,23,26,1,11,11,5,1,1,1,5,6,7,21,1,1,10,1,1,29,1,1,6,19,1,1,5,1,30,1,15,1,3,15,15,23,6,1,5,1,1,1,1,3,1,1,17,7,1,11,6,13,2,17,1,3,1,22,1,1,23,13,1,3,1,1,1,1,13,22,1,22,1,10,1,23,15,14,1,30,1,1,29,17,3,1,19,1,7,14,2,1,14,23,2,30,1,19,1,1,10,19,23,1,1,1,1,1,1,1,1,1,1,1,26,30,26,1,2,2,21,1,1,1,1,1,1,1,1,1,22,15,21,15,13,26,1,1,1,1,21,1,13,30,1,22,1,14,1,21,15,14,21,1,22,1,1,1,11,1,6,6,1,1,1,13,3,10,23,15,30,1,1,7,19,7,1,30,15,1,7,1,11,2,17,14,17,21,1,1,17,1,3,23,1,1,11,21,1,1,1,1,10,1,11,1,1,1,1,6,22,1,1,6,26,23,1,1,11,10,1,6,6,1,26,1,1,1,1,1,1,1,1,1,22,1,19,13,1,1,2,10,1,26,1,1,5,3,10,13,11,17,1,1,23,1,7,5,1,1,11,22,1,23,1,1,1,29,26,2,1,19,15,13,29,1,1,19,26,1,11,26,11,1,6,1,1,26,21,3,2,1,1,10,1,1,21,15,1,1,23,1,2,5,1,3,1,1,1,14,5,1,21,1,30,11,5,21,14,14,1,1,19,10,1,1,1,1,22,14,1,7,23,1,29,23,1,1,1,17,1,1,1,15,17,22,26,1,1,1,1,1,13,13,11,1,1,1,1,5,10,1,1,1,15,1,5,1,1,1,22,1,15,11,1,1,1,13,1,1,13,1,23,1,1,6,1,6,1,1,19,1,17,1,13,1,22,1,1,1,1,13,6,1,1,1,19,7,1,23,1,1,21,1,1,6,1,3,29,21,15,1,1,1,1,1,1,1,14,13,1,1,1,1,1,1,1,1,1,2,10,21,11,17,23,30,1,30,3,11,1,1,1,1,22,2,1,1,11,6,23,3,1,1,1,1,1,1,1,1,1,23,1,23,21,3,19,1,1,26,30,1,1,1,30,1,1,1,5,1,1,1,1,29,1,7,1,1,2,1,30,7,17,7,13,1,1,29,1,1,1,1,26,1,1,6,13,1,1,1,11,1,30,1,14,11,30,1,1,1,1,1,14,1,26,6,26,1,7,23,1,11,13,2,23,1,7,22,1,1,1,5,22,15,1,11,1,21,1,1,13,26,30,1,22,1,1,14,29,1,1,1,1,1,30,2,1,1,29,1,1,3,21,11,1,3,22,5,6,10,1,1,1,1,26,11,1,22,14,1,14,1,21,1,10,23,1,13,1,29,19,1,14,1,22,1,1,1,1,29,29,3,1,1,19,10,5,1,1,1,22,1,1,14,2,1,1,1,1,23,1,6,1,1,2,1,15,10,3,22,1,1,1,1,1,1,11,1,1,5,1,1,6,30,1,17,1,1,2,1,1,5,1,1,19,10,29,22,1,10,3,1,6,1,7,13,1,3,29,1,1,1,1,26,1,1,1,21,1,29,1,1,5,1,1,5,1,1,13,1,1,1,1,1,1,22,1,1,5,1,2,30,1,14,1,1,5,1,11,1,14,11,1,13,15,11,1,1,29,5,26,26,1,1,1,14,1,1,1,10,1,1,30,30,1,6,2,1,5,1,1,1,19,13,3,10,1,1,1,3,1,1,1,1,1,15,1,13,2,1,1,1,1,6,11,1,1,1,1,23,17,22,15,1,1,3,19,10,1,7,1,23,1,1,1,15,23,11,1,22,1,19,1,1,1,1,7,1,1,1,1,1,5,19,6,30,1,6,14,1,1,1,10,1,7,1,5,1,1,1,1,1,15,1,17,7,7,29,23,26,6,3,10,3,2,10,1,5,22,1,1,1,1,1,1,2,30,26,21,1,1,1,1,1,1,29,1,7,1,11,17,1,6,6,7,1,17,22,1,17,1,26,1,1,23,1,1,1,1,1,1,1,19,1,7,1,2,30,1,1,30,17,1,1,21,30,29,1,1,1,7,26,1,14,1,1,5,1,3,7,1,1,1,10,1,15,1,1,1,1,15,1,11,1,1,1,1,29,13,23,10,1,1,1,1,5,13,1,1,1,1,26,1,1,17,1,1,1,19,26,1,1,1,22,1,23,13,19,1,29,1,1,29,30,5,1,2,1,23,5,26,1,1,1,10,1,21,22,15,1,3,1,1,1,15,1,2,1,1,22,29,1,1,1,17,19,19,1,3,1,1,1,1,22,3,1,1,6,1,3,1,1,10,21,1,1,21,6,1,1,1,13,2,5,3,1,15,15,22,1,1,1,2,1,2,3,1,14,1,1,10,1,26,13,6,13,23,14,1,14,1,3,17,7,1,17,1,1,17,1,26,30,30,10,22,1,1,3,5,21,1,1,14,1,1,1,1,5,26,1,29,19,17,23,23,11,1,7,2,15,14,1,19,1,13,1,15,14,1,29,2,1,2,26,5,19,1,14,21,19,1,1,1,1,21,1,1,1,1,1,29,14,1,1,1,1,7,1,15,1,21,13,1,1,13,1,15,1,6,1,1,1,1,1,2,7,1,1,26,14,3,1,1,1,1,1,30,10,1,21,13,1,1,1,17,1,19,11,1,1,1,29,13,1,1,30,1,30,1,19,10,22,10,6,1,21,15,1,22,1,1,29,26,1,19,1,7,1,1,17,15,1,7,1,1,10,22,13,1,22,1,1,17,1,26,1,1,11,1,17,1,26,1,1,11,6,1,1,3,1,3,6,2,1,1,29,1,3,13,17,30,1,1,30,1,1,1,1,2,1,1,29,1,1,14,5,1,14,5,1,1,2,2,14,23,5,10,19,10,1,1,1,1,22,1,21,3,23,1,1,1,1,15,1,26,6,1,30,10,7,15,1,1,1,1,10,19,1,2,1,1,26,1,1,2,21,1,22,23,5,29,1,1,1,30,14,1,1,1,5,1,1,1,1,1,6,1,1,6,2,1,1,7,1,1,21,15,11,1,30,23,1,1,1,1,1,17,1,1,15,1,1,17,15,10,3,1,17,1,1,30,30,1,11,3,1,1,22,1,11,2,29,1,22,14,1,29,17,2,19,1,1,1,1,1,23,3,23,26,1,6,1,1,2,3,26,10,1,7,1,7,1,5,7,15,21,1,6,5,23,7,5,19,3,11,17,1,10,1,1,1,7,1,1,1,1,29,1,14,29,1,1,5,30,1,11,29,14,19,1,1,5,1,22,1,1,7,6,26,3,21,1,30,1,13,1,1,5,1,1,29,1,1,29,1,21,1,14,14,1,29,14,1,1,14,1,1,13,26,15,1,1,23,10,30,1,1,17,1,1,1,1,1,17,2,1,5,13,23,1,7,14,1,3,14,1,1,7,23,1,23,6,15,17,1,19,1,1,17,1,11,1,19,10,17,21,1,1,1,7,1,11,1,13,1,1,22,22,7,26,1,2,21,19,19,1,30,11,23,17,1,19,10,1,29,1,7,15,1,1,21,23,11,6,2,11,30,1,26,1,2,13,26,6,14,1,1,1,1,1,1,1,1,1,21,1,1,1,1,1,1,1,13,1]")));
        System.out.println(solution_other.numberOfGoodSubsets(InputUtil.toIntegerArray("[1,26,1,1,21,1,3,13,1,1,1,26,29,29,6,10,29,1,1,11,15,6,14,1,17,1,1,30,21,1,17,1,1,1,23,1,7,17,15,1,1,1,14,22,11,22,17,1,19,1,2,21,29,1,22,1,1,14,22,1,14,1,1,1,1,17,1,1,1,3,1,14,19,1,1,1,1,21,26,1,1,1,13,1,1,30,21,1,1,1,1,7,1,1,7,13,6,1,29,29,1,1,23,1,19,10,10,1,1,2,1,1,23,15,5,15,1,1,19,15,1,1,14,1,7,26,1,1,2,13,19,1,3,22,1,1,29,1,7,1,1,1,1,3,1,1,1,3,1,1,1,2,17,1,1,1,1,1,19,5,1,1,1,19,30,23,1,1,2,1,1,7,17,1,1,1,30,21,1,3,1,5,15,1,26,1,1,21,22,19,1,13,6,15,19,2,1,1,1,1,11,17,21,29,23,26,10,1,30,1,14,1,1,21,1,30,1,1,1,11,22,19,21,30,11,14,1,1,3,7,17,10,10,3,1,1,1,10,1,15,1,15,15,1,1,1,1,1,21,14,6,1,17,1,1,1,17,10,3,1,22,21,1,1,23,19,1,5,5,5,10,1,29,1,1,1,1,7,1,15,1,6,6,1,1,1,13,1,1,29,17,1,1,1,6,1,1,2,13,10,29,1,13,21,7,10,1,1,1,7,29,15,29,17,5,30,1,11,1,23,1,1,1,5,1,30,6,1,5,6,1,11,17,26,1,1,13,1,26,1,11,13,1,11,1,1,1,30,1,1,1,14,19,1,1,15,21,1,1,2,1,1,19,1,26,1,5,22,13,1,1,11,7,29,3,26,30,19,10,1,7,1,22,1,6,2,1,23,26,1,11,11,5,1,1,1,5,6,7,21,1,1,10,1,1,29,1,1,6,19,1,1,5,1,30,1,15,1,3,15,15,23,6,1,5,1,1,1,1,3,1,1,17,7,1,11,6,13,2,17,1,3,1,22,1,1,23,13,1,3,1,1,1,1,13,22,1,22,1,10,1,23,15,14,1,30,1,1,29,17,3,1,19,1,7,14,2,1,14,23,2,30,1,19,1,1,10,19,23,1,1,1,1,1,1,1,1,1,1,1,26,30,26,1,2,2,21,1,1,1,1,1,1,1,1,1,22,15,21,15,13,26,1,1,1,1,21,1,13,30,1,22,1,14,1,21,15,14,21,1,22,1,1,1,11,1,6,6,1,1,1,13,3,10,23,15,30,1,1,7,19,7,1,30,15,1,7,1,11,2,17,14,17,21,1,1,17,1,3,23,1,1,11,21,1,1,1,1,10,1,11,1,1,1,1,6,22,1,1,6,26,23,1,1,11,10,1,6,6,1,26,1,1,1,1,1,1,1,1,1,22,1,19,13,1,1,2,10,1,26,1,1,5,3,10,13,11,17,1,1,23,1,7,5,1,1,11,22,1,23,1,1,1,29,26,2,1,19,15,13,29,1,1,19,26,1,11,26,11,1,6,1,1,26,21,3,2,1,1,10,1,1,21,15,1,1,23,1,2,5,1,3,1,1,1,14,5,1,21,1,30,11,5,21,14,14,1,1,19,10,1,1,1,1,22,14,1,7,23,1,29,23,1,1,1,17,1,1,1,15,17,22,26,1,1,1,1,1,13,13,11,1,1,1,1,5,10,1,1,1,15,1,5,1,1,1,22,1,15,11,1,1,1,13,1,1,13,1,23,1,1,6,1,6,1,1,19,1,17,1,13,1,22,1,1,1,1,13,6,1,1,1,19,7,1,23,1,1,21,1,1,6,1,3,29,21,15,1,1,1,1,1,1,1,14,13,1,1,1,1,1,1,1,1,1,2,10,21,11,17,23,30,1,30,3,11,1,1,1,1,22,2,1,1,11,6,23,3,1,1,1,1,1,1,1,1,1,23,1,23,21,3,19,1,1,26,30,1,1,1,30,1,1,1,5,1,1,1,1,29,1,7,1,1,2,1,30,7,17,7,13,1,1,29,1,1,1,1,26,1,1,6,13,1,1,1,11,1,30,1,14,11,30,1,1,1,1,1,14,1,26,6,26,1,7,23,1,11,13,2,23,1,7,22,1,1,1,5,22,15,1,11,1,21,1,1,13,26,30,1,22,1,1,14,29,1,1,1,1,1,30,2,1,1,29,1,1,3,21,11,1,3,22,5,6,10,1,1,1,1,26,11,1,22,14,1,14,1,21,1,10,23,1,13,1,29,19,1,14,1,22,1,1,1,1,29,29,3,1,1,19,10,5,1,1,1,22,1,1,14,2,1,1,1,1,23,1,6,1,1,2,1,15,10,3,22,1,1,1,1,1,1,11,1,1,5,1,1,6,30,1,17,1,1,2,1,1,5,1,1,19,10,29,22,1,10,3,1,6,1,7,13,1,3,29,1,1,1,1,26,1,1,1,21,1,29,1,1,5,1,1,5,1,1,13,1,1,1,1,1,1,22,1,1,5,1,2,30,1,14,1,1,5,1,11,1,14,11,1,13,15,11,1,1,29,5,26,26,1,1,1,14,1,1,1,10,1,1,30,30,1,6,2,1,5,1,1,1,19,13,3,10,1,1,1,3,1,1,1,1,1,15,1,13,2,1,1,1,1,6,11,1,1,1,1,23,17,22,15,1,1,3,19,10,1,7,1,23,1,1,1,15,23,11,1,22,1,19,1,1,1,1,7,1,1,1,1,1,5,19,6,30,1,6,14,1,1,1,10,1,7,1,5,1,1,1,1,1,15,1,17,7,7,29,23,26,6,3,10,3,2,10,1,5,22,1,1,1,1,1,1,2,30,26,21,1,1,1,1,1,1,29,1,7,1,11,17,1,6,6,7,1,17,22,1,17,1,26,1,1,23,1,1,1,1,1,1,1,19,1,7,1,2,30,1,1,30,17,1,1,21,30,29,1,1,1,7,26,1,14,1,1,5,1,3,7,1,1,1,10,1,15,1,1,1,1,15,1,11,1,1,1,1,29,13,23,10,1,1,1,1,5,13,1,1,1,1,26,1,1,17,1,1,1,19,26,1,1,1,22,1,23,13,19,1,29,1,1,29,30,5,1,2,1,23,5,26,1,1,1,10,1,21,22,15,1,3,1,1,1,15,1,2,1,1,22,29,1,1,1,17,19,19,1,3,1,1,1,1,22,3,1,1,6,1,3,1,1,10,21,1,1,21,6,1,1,1,13,2,5,3,1,15,15,22,1,1,1,2,1,2,3,1,14,1,1,10,1,26,13,6,13,23,14,1,14,1,3,17,7,1,17,1,1,17,1,26,30,30,10,22,1,1,3,5,21,1,1,14,1,1,1,1,5,26,1,29,19,17,23,23,11,1,7,2,15,14,1,19,1,13,1,15,14,1,29,2,1,2,26,5,19,1,14,21,19,1,1,1,1,21,1,1,1,1,1,29,14,1,1,1,1,7,1,15,1,21,13,1,1,13,1,15,1,6,1,1,1,1,1,2,7,1,1,26,14,3,1,1,1,1,1,30,10,1,21,13,1,1,1,17,1,19,11,1,1,1,29,13,1,1,30,1,30,1,19,10,22,10,6,1,21,15,1,22,1,1,29,26,1,19,1,7,1,1,17,15,1,7,1,1,10,22,13,1,22,1,1,17,1,26,1,1,11,1,17,1,26,1,1,11,6,1,1,3,1,3,6,2,1,1,29,1,3,13,17,30,1,1,30,1,1,1,1,2,1,1,29,1,1,14,5,1,14,5,1,1,2,2,14,23,5,10,19,10,1,1,1,1,22,1,21,3,23,1,1,1,1,15,1,26,6,1,30,10,7,15,1,1,1,1,10,19,1,2,1,1,26,1,1,2,21,1,22,23,5,29,1,1,1,30,14,1,1,1,5,1,1,1,1,1,6,1,1,6,2,1,1,7,1,1,21,15,11,1,30,23,1,1,1,1,1,17,1,1,15,1,1,17,15,10,3,1,17,1,1,30,30,1,11,3,1,1,22,1,11,2,29,1,22,14,1,29,17,2,19,1,1,1,1,1,23,3,23,26,1,6,1,1,2,3,26,10,1,7,1,7,1,5,7,15,21,1,6,5,23,7,5,19,3,11,17,1,10,1,1,1,7,1,1,1,1,29,1,14,29,1,1,5,30,1,11,29,14,19,1,1,5,1,22,1,1,7,6,26,3,21,1,30,1,13,1,1,5,1,1,29,1,1,29,1,21,1,14,14,1,29,14,1,1,14,1,1,13,26,15,1,1,23,10,30,1,1,17,1,1,1,1,1,17,2,1,5,13,23,1,7,14,1,3,14,1,1,7,23,1,23,6,15,17,1,19,1,1,17,1,11,1,19,10,17,21,1,1,1,7,1,11,1,13,1,1,22,22,7,26,1,2,21,19,19,1,30,11,23,17,1,19,10,1,29,1,7,15,1,1,21,23,11,6,2,11,30,1,26,1,2,13,26,6,14,1,1,1,1,1,1,1,1,1,21,1,1,1,1,1,1,1,13,1]")));
    }

    public static void main(String[] args) throws Exception {
        LC1994 an = new LC1994();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
